package com.linyaonan.leetcode.medium._1079;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 * 你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
 *
 *  
 *
 * 示例 1：
 *
 * 输入："AAB"
 * 输出：8
 * 解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
 * 示例 2：
 *
 * 输入："AAABBC"
 * 输出：188
 *  
 *
 * 提示：
 *
 * 1 <= tiles.length <= 7
 * tiles 由大写英文字母组成
 *
 * @author: Lin
 * @date: 2020/1/15
 */
public class LetterTilePossibilities {
    char[] c;
    Set<String> set;
    public int numTilePossibilities(String tiles) {
        c = tiles.toCharArray();
        set = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        List<Character> chars = new ArrayList<>();
        for (char cc : c) {
            chars.add(cc);
        }
        // 多个长度数值需要多次回溯
        for (int i = 1; i <= c.length; i++) {
            backTracing(sb, i, chars);
        }
        return set.size();
    }

    private void backTracing(StringBuilder sb, int targetCount, List<Character> chars) {
        if (sb.length() == targetCount) {
            set.add(sb.toString());
            return;
        }
        for (int j = 0; j < chars.size(); j++) {
            Character remove = chars.remove(j);
            sb.append(remove);
            // 递归
            backTracing(sb, targetCount, chars);
            // 回溯
            sb.delete(sb.length() - 1, sb.length());
            chars.add(j, remove);
        }
    }
}
